Contiguous Allocation

• 主記憶體必須要能支持和。
• 因為資源有限，所以需要有效率的進行分配。
• 此方法是一種早期的方法。
• 主記憶體通常分為兩區：

1. Resident operating system通常使用保存在低記憶體中。
2. 然後再由user processes保持高記憶體。
3. 每個process包含在單個連續的記憶體部分中。

• Relocation registers是用來保護，還有從那邊改變跟。

1. Base register包含最小physical address的值。
2. Limit register含logical address的範圍，每個logical address必小於limit register。
3. 會動態映射。
4. MMU允許如kernel code可以是短暫的，和可以改變尺寸等動作。

Multiple-partition allocation

• multiprogramming的程度受分區數量的限制。
• Variable-partition的尺寸是要有效率的，也就是說尺寸是合Process的需求。
• Hole：是可用的記憶體區塊；各個hole的大小是分散在記憶體中。
• 當一個process到達，便會從一個足夠大的hole中分配記憶體以容納它。
• process退出free partition，和鄰近的做結合。
• OS維持以下兩種資訊：

1. allocated partition
2. free partition(hole)

Dynamic Storage-Allocation Problem

• 如何從free hole的列表中滿足size n的要求：

1. First-fit：分配夠大的第一個hole。
2. Best-fit：分配足夠大的最小hole，必須搜尋整個列表，除非是按尺寸搜尋。
   1-產生最小的剩餘hole。
3. Worst-fit：分配最大的hole，也需要搜尋整個列表。
   1-產生最大的剩餘hole。

• First-fit跟best-fit就速度與儲存率來說都比worst-fit要更好。

Fragmentation

• External Fragmentation：存在整個記憶體空間中去滿足請求，但這並不連續。
• Internal Fragmentation：被分配的記憶體比請求的記憶體要稍微再大一些，而這個尺寸差異是分區內部的記憶體，但並未使用。
• First fit的分析揭露了若分配給N個區塊，就會有0.N個區塊遺失，便成了碎片(fragmentation)。
• 藉由壓實(compaction)來減少外部碎片：

1. 將隨機記憶體內容的所有可用記憶體存放在一個大區塊中。
2. 壓實只可能在如果relocation是dynamic，則在execution time時完成。
3. 關於I/O的問題：
   1-在I/O中若涉及記憶體，將會鎖定工作。
   2-只有在I/O進入OS緩衝器時才能做。

Segmentation

• 支持使用者查看記憶體的一種記憶體管理方案。
• Program是多個segment的集合，如：

1. 主記憶體。
2. 功能。
3. 方法。
4. 物件等等。

Segmentation Architecture

• Logical address由2個元組所組成：

1. segment-number
2. segment-offset

• Segment table：映照到二維的physical addresses，且每個都有：

1. base：含segment駐留在記憶體中的起始physiccal address。
2. limit：指定segment的長度。

• Segment-table base register(STBR)：指出segment table在記憶體中的位置。
• Segment-table length register(STLR)：指示程式使用segment的數量。

1. segment的數量S，如果S是小於STLR的話，則此為合法。

• Protection：

1. 與每個segment table有關的每個項目：
   1-驗證bit=0的話，則為不合法的segment。
   2-擁有read、write、execute的特權。

• 保護和segment有關聯的bit；code sharing是發生在segment這個級別中。
• 由於segment長度有所不同，所以記憶體分配是個dynamic storage-allocation的問題。